﻿using ImageK.Gui;
using ImageK.Process;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ImageK.Java;
using ImageK.Exceptions;
using System.Collections;

namespace ImageK.Plugin.Filter
{
    public class ThresholdToSelection : PlugInFilter
    {
        ImagePlus image;
        ImageProcessor ip;
        float min, max;
        int w, h;
        bool _showStatus;

        static double
            PROGRESS_FRACTION_OUTLINING = 0.9; //fraction of progress bar for the first phase (tracing outlines)

        public void run(ImageProcessor ip)
        {
            _showStatus = true;
            image.setRoi(convert(ip));
        }

        /** Returns a selection created from the thresholded pixels in the
            specified image, or null if there are no thresholded pixels. */
        public static Roi run(ImagePlus imp)
        {
            ThresholdToSelection tts = new ThresholdToSelection();
            return tts.convert(imp.getProcessor());
        }

        /** Returns a selection created from the thresholded pixels in the
            specified image, or null if there are no thresholded pixels. */
        public Roi convert(ImageProcessor ip)
        {
            this.ip = ip;
            min = (float)ip.getMinThreshold();
            max = (float)ip.getMaxThreshold();
            w = ip.getWidth();
            h = ip.getHeight();
            return getRoi();
        }

        bool selected(int x, int y)
        {
            float v = ip.getf(x, y);
            return v >= min && v <= max;
        }

        /*
         * This class implements a Cartesian polygon in progress.
         * The edges are supposed to be parallel to the x or y axis.
         * It is implemented as a deque to be able to add points to both
         * sides.
         */
        class Outline
        {
            int[] x, y;
            int first, last, reserved;
            int GROW = 10; // default extra (spare) space when enlarging arrays (similar performance with 6-20)

            public Outline()
            {
                reserved = GROW;
                x = new int[reserved];
                y = new int[reserved];
                first = last = GROW / 2;
            }

            /** Makes sure that enough free space is available at the beginning and end of the list, by enlarging the arrays if required */
            private void needs(int neededAtBegin, int neededAtEnd)
            {
                if (neededAtBegin > first || neededAtEnd > reserved - last)
                {
                    int extraSpace =
                        Math.Max(GROW,
                            Math.Abs(x[last - 1] - x[first])); //reserve more space for outlines that span large x range
                    int newSize = reserved + neededAtBegin + neededAtEnd + extraSpace;
                    int newFirst = neededAtBegin + extraSpace / 2;
                    int[] newX = new int[newSize];
                    int[] newY = new int[newSize];
                    System.Array.Copy(x, first, newX, newFirst, last - first);
                    System.Array.Copy(y, first, newY, newFirst, last - first);
                    x = newX;
                    y = newY;
                    last += newFirst - first;
                    first = newFirst;
                    reserved = newSize;
                }
            }

            /** Adds point x, y at the end of the list */
            public void append(int x, int y)
            {
                if (last - first >= 2 && collinear(this.x[last - 2], this.y[last - 2], this.x[last - 1],
                        this.y[last - 1], x, y))
                {
                    this.x[last - 1] = x; //replace previous point
                    this.y[last - 1] = y;
                }
                else
                {
                    needs(0, 1); //new point
                    this.x[last] = x;
                    this.y[last] = y;
                    last++;
                }
            }

            /** Adds point x, y at the beginning of the list */
            public void prepend(int x, int y)
            {
                if (last - first >= 2 &&
                    collinear(this.x[first + 1], this.y[first + 1], this.x[first], this.y[first], x, y))
                {
                    this.x[first] = x; //replace previous point
                    this.y[first] = y;
                }
                else
                {
                    needs(1, 0); //new point
                    first--;
                    this.x[first] = x;
                    this.y[first] = y;
                }
            }

            /** Merge with another Outline by adding it at the end. Thereafter, the other outline must not be used any more. */
            public void append(Outline o)
            {
                int size = last - first;
                int oSize = o.last - o.first;
                if (size <= o.first && oSize > reserved - last)
                {
                    // we don't have enough space in our own array but in that of 'o'
                    System.Array.Copy(x, first, o.x, o.first - size, size); // so prepend our own data to that of 'o'
                    System.Array.Copy(y, first, o.y, o.first - size, size);
                    x = o.x;
                    y = o.y;
                    first = o.first - size;
                    last = o.last;
                    reserved = o.reserved;
                }
                else
                {
                    // append to our own array
                    needs(0, oSize);
                    System.Array.Copy(o.x, o.first, x, last, oSize);
                    System.Array.Copy(o.y, o.first, y, last, oSize);
                    last += oSize;
                }
            }

            /** Merge with another Outline by adding it at the beginning. Thereafter, the other outline must not be used any more. */
            public void prepend(Outline o)
            {
                int size = last - first;
                int oSize = o.last - o.first;
                if (size <= o.reserved - o.last && oSize > first)
                {
                    // we don't have enough space in our own array but in that of 'o'
                    System.Array.Copy(x, first, o.x, o.last, size); // so append our own data to that of 'o'
                    System.Array.Copy(y, first, o.y, o.last, size);
                    x = o.x;
                    y = o.y;
                    first = o.first;
                    last = o.last + size;
                    reserved = o.reserved;
                }
                else
                {
                    // prepend to our own array
                    needs(oSize, 0);
                    first -= oSize;
                    System.Array.Copy(o.x, o.first, x, first, oSize);
                    System.Array.Copy(o.y, o.first, y, first, oSize);
                }
            }

            public Polygon getPolygon()
            {
                // optimize out intermediate points of straight lines (created, e.g., by merging outlines)
                int i, j = first+1;
                for (i=first+1; i+1<last; j++)
                {
                    if (collinear(x[j - 1], y[j - 1], x[j], y[j], x[j + 1], y[j + 1]))
                    {
                        // merge i + 1 into i
                        last--;
                        continue;
                    }
                    if (i != j)
                    {
                        x[i] = x[j];
                        y[i] = y[j];
                    }
                    i++;
                }
                // wraparound
                if (collinear(x[j - 1], y[j - 1], x[j], y[j], x[first], y[first]))
                    last--;
                else
                {
                    x[i] = x[j];
                    y[i] = y[j];
                }
                if (last - first > 2 && collinear(x[last - 1], y[last - 1], x[first], y[first], x[first + 1], y[first + 1]))
                    first++;

                int count = last - first;
                int[] xNew = new int[count];
                int[] yNew = new int[count];
                System.Array.Copy(x, first, xNew, 0, count);
                System.Array.Copy(y, first, yNew, 0, count);
                return new Polygon(xNew, yNew, count);
            }

            /** Returns whether three points are on one straight line */
            bool collinear(int x1, int y1, int x2, int y2, int x3, int y3)
            {
                return (x2-x1)*(y3-y2) == (y2-y1)*(x3-x2);
            }

            public string toString()
            {
                String res = "[first:" + first + ",last:" + last +
                             ",reserved:" + reserved + ":";
                if (last > x.Length) System.Console.WriteLine("ERROR!");
                int nmax = 10;  //don't print more coordinates than this
                for (int i = first; i < last && i < x.Length; i++)
                {
                    if (last-first > nmax && i-first > nmax/2)
                    {
                        i = last - nmax/2;
                        res += "...";
                        nmax = last-first; //dont check again
                    }
                    else
                        res += "(" + x[i] + "," + y[i] + ")";
                }
                return res + "]";
            }

        }

        /*
         * Construct all outlines simultaneously by traversing the rows from top to bottom.
         * The points are added such that for each pair of consecutive points, the inner
         * part is on the left, i.e., the outline encloses filled areas in the
         * counterclockwise direction. The outline of empty areas (holes) runs clockwise.
         *
         * thisRow[x + 1] indicates whether the pixel at (x, y) is selected (inside threshold bounds).
         * prevRow[x + 1] indicates whether the pixel at (x, y - 1) is selected.
         *
         * outline[x] is the outline that is currently unclosed at the top-left corner of pixel(x, y);
         * outline[x + 1] is at the top-right corner of pixel(x, y).
         *
         * If the pixel (x, y - 1) has an outline at its bottom and right sides (merging in its
         * lower right corner) and this outline should continue as left & top edges of pixel (x + 1, y),
         * <code>xAfterLowerRightCorner</code> is set to x + 1 (the pixel coordinate where this
         * has to be taken into account), and <code>oAfterLowerRightCorner</code> is the outline that
         * should continue at the left side of pixel (xAfterLowerRightCorner, y) to higher y.
         * (Without the code with xAfterLowerRightCorner, etc., this case of 8-connected pixels
         * would result in disjunct outlines, e.g. a one-pixel-wide line with angle between
         * 0 and -90 deg would be converted to many separate rectangular segments).
         */
        Roi getRoi()
        {
            if (_showStatus)
                IJ.ShowStatus("Converting threshold to selection");
            bool[] prevRow, thisRow;
            ArrayList polygons = new ArrayList();
            Outline[] outline;
            int progressInc = Math.Max(h/50, 1);

            prevRow = new bool[w + 2];
            thisRow = new bool[w + 2];
            outline = new Outline[w + 1];

            for (int y = 0; y <= h; y++)
            {
                bool[] b = prevRow; prevRow = thisRow; thisRow = b;
                int xAfterLowerRightCorner = -1;       //x at right of 8-connected (not 4-connected) pixels NW-SE
                Outline oAfterLowerRightCorner = null; //there, continue this outline towards south
                thisRow[1] = y < h ? selected(0, y) : false;
                for (int x = 0; x <= w; x++)
                {
                    if (y < h && x < w - 1)
                        thisRow[x + 2] = selected(x + 1, y);  //we need to read one pixel ahead
                    else if (x < w - 1)
                        thisRow[x + 2] = false;
                    //IJ.log(x+","+y+": "+thisRow[x + 1]+(x==xAfterLowerRightCorner ? " Corner" : "")+" left="+outline[x]+(x < w ? " right="+outline[x+1] : ""));
                    if (thisRow[x + 1])
                    {  // i.e., pixel (x,y) is selected
                        if (!prevRow[x + 1])
                        {
                            // Upper edge of selected area:
                            // - left and right outlines are null: new outline
                            // - left null: append (line to left)
                            // - right null: prepend (line to right), or prepend&append (after lower right corner, two borders from one corner)
                            // - left == right: close (end of hole above) unless we can continue at the right
                            // - left != right: merge (prepend) unless we can continue at the right
                            if (outline[x] == null)
                            {
                                if (outline[x + 1] == null)
                                {
                                    outline[x + 1] = outline[x] = new Outline();
                                    outline[x].append(x + 1, y);
                                    outline[x].append(x, y);
                                }
                                else
                                {
                                    outline[x] = outline[x + 1];  // line from top-right to top-left
                                    outline[x + 1] = null;
                                    outline[x].append(x, y);
                                }
                            }
                            else if (outline[x + 1] == null)
                            {
                                if (x == xAfterLowerRightCorner)
                                {
                                    outline[x + 1] = outline[x];
                                    outline[x] = oAfterLowerRightCorner;
                                    outline[x].append(x, y);
                                    outline[x + 1].prepend(x + 1, y);
                                }
                                else
                                {
                                    outline[x + 1] = outline[x];
                                    outline[x] = null;
                                    outline[x + 1].prepend(x + 1, y);
                                }
                            }
                            else if (outline[x + 1] == outline[x])
                            {
                                if (x < w - 1 && y < h && x != xAfterLowerRightCorner
                                        && !thisRow[x + 2] && prevRow[x + 2])
                                { //at lower right corner & next pxl deselected
                                    outline[x] = null;
                                    //outline[x+1] unchanged
                                    outline[x + 1].prepend(x + 1, y);
                                    xAfterLowerRightCorner = x + 1;
                                    oAfterLowerRightCorner = outline[x + 1];
                                }
                                else
                                {
                                    //System.err.println("subtract " + outline[x]);
                                    polygons.Add(outline[x].getPolygon()); // MINUS (add inner hole)
                                    outline[x + 1] = null;
                                    outline[x] = (x == xAfterLowerRightCorner) ? oAfterLowerRightCorner : null;
                                }
                            }
                            else
                            {
                                outline[x].prepend(outline[x + 1]);     // merge
                                for (int x1 = 0; x1 <= w; x1++)
                                    if (x1 != x + 1 && outline[x1] == outline[x + 1])
                                    {
                                        outline[x1] = outline[x];        // after merging, replace old with merged
                                        outline[x + 1] = null;           // no line continues at the right
                                        outline[x] = (x == xAfterLowerRightCorner) ? oAfterLowerRightCorner : null;
                                        break;
                                    }
                                if (outline[x + 1] != null)
                                    throw new RuntimeException("assertion failed");
                            }
                        }
                        if (!thisRow[x])
                        {
                            // left edge
                            if (outline[x] == null)
                                throw new RuntimeException("assertion failed");
                            outline[x].append(x, y + 1);
                        }
                    }
                    else
                    {  // !thisRow[x + 1], i.e., pixel (x,y) is deselected
                        if (prevRow[x + 1])
                        {
                            // Lower edge of selected area:
                            // - left and right outlines are null: new outline
                            // - left == null: prepend
                            // - right == null: append, or append&prepend (after lower right corner, two borders from one corner)
                            // - right == left: close unless we can continue at the right
                            // - right != left: merge (append) unless we can continue at the right
                            if (outline[x] == null)
                            {
                                if (outline[x + 1] == null)
                                {
                                    outline[x] = outline[x + 1] = new Outline();
                                    outline[x].append(x, y);
                                    outline[x].append(x + 1, y);
                                }
                                else
                                {
                                    outline[x] = outline[x + 1];
                                    outline[x + 1] = null;
                                    outline[x].prepend(x, y);
                                }
                            }
                            else if (outline[x + 1] == null)
                            {
                                if (x == xAfterLowerRightCorner)
                                {
                                    outline[x + 1] = outline[x];
                                    outline[x] = oAfterLowerRightCorner;
                                    outline[x].prepend(x, y);
                                    outline[x + 1].append(x + 1, y);
                                }
                                else
                                {
                                    outline[x + 1] = outline[x];
                                    outline[x] = null;
                                    outline[x + 1].append(x + 1, y);
                                }
                            }
                            else if (outline[x + 1] == outline[x])
                            {
                                //System.err.println("add " + outline[x]);
                                if (x < w - 1 && y < h && x != xAfterLowerRightCorner
                                        && thisRow[x + 2] && !prevRow[x + 2])
                                { //at lower right corner & next pxl selected
                                    outline[x] = null;
                                    //outline[x+1] unchanged
                                    outline[x + 1].append(x + 1, y);
                                    xAfterLowerRightCorner = x + 1;
                                    oAfterLowerRightCorner = outline[x + 1];
                                }
                                else
                                {
                                    polygons.Add(outline[x].getPolygon());   // PLUS (add filled outline)
                                    outline[x + 1] = null;
                                    outline[x] = x == xAfterLowerRightCorner ? oAfterLowerRightCorner : null;
                                }
                            }
                            else
                            {
                                if (x < w - 1 && y < h && x != xAfterLowerRightCorner
                                        && thisRow[x + 2] && !prevRow[x + 2])
                                { //at lower right corner && next pxl selected
                                    outline[x].append(x + 1, y);
                                    outline[x + 1].prepend(x + 1, y);
                                    xAfterLowerRightCorner = x + 1;
                                    oAfterLowerRightCorner = outline[x];
                                    // outline[x + 1] unchanged (the one at the right-hand side of (x, y-1) to the top)
                                    outline[x] = null;
                                }
                                else
                                {
                                    outline[x].append(outline[x + 1]);         // merge
                                    for (int x1 = 0; x1 <= w; x1++)
                                        if (x1 != x + 1 && outline[x1] == outline[x + 1])
                                        {
                                            outline[x1] = outline[x];        // after merging, replace old with merged
                                            outline[x + 1] = null;           // no line continues at the right
                                            outline[x] = (x == xAfterLowerRightCorner) ? oAfterLowerRightCorner : null;
                                            break;
                                        }
                                    if (outline[x + 1] != null)
                                        throw new RuntimeException("assertion failed");
                                }
                            }
                        }
                        if (thisRow[x])
                        {
                            // right edge
                            if (outline[x] == null)
                                throw new RuntimeException("assertion failed");
                            outline[x].prepend(x, y + 1);
                        }
                    }
                }
                if (y%progressInc==0)
                {
                    // if (Thread.currentThread().isInterrupted()) return null;
                    if (!Thread.CurrentThread.IsAlive) return null;
                    if (_showStatus)
                        IJ.showProgress(y*(PROGRESS_FRACTION_OUTLINING/h));
                }
            }

            if (polygons.Count==0)
                return null;
            if (_showStatus) IJ.ShowStatus("Converting threshold to selection...");
            //todo:
            // GeneralPath path = new GeneralPath(GeneralPath.WIND_EVEN_ODD);
            // progressInc = Math.Max(polygons.Count/10, 1);
            // for (int i = 0; i < polygons.Count; i++)
            // {
            //     path.append((Polygon)polygons[i], false);
            //     // if (Thread.currentThread().isInterrupted()) return null;
            //     if (!Thread.CurrentThread.IsAlive) return null;
            //     if (showStatus && i%progressInc==0)
            //         IJ.showProgress(PROGRESS_FRACTION_OUTLINING + i*(1.0-PROGRESS_FRACTION_OUTLINING)/polygons.Count);
            // }
            //
            // ShapeRoi shape = new ShapeRoi(path);
            // Roi roi = shape!=null ? shape.trySimplify() : null; // try to convert to non-composite ROI
            Roi roi = null;
            if (_showStatus)
                IJ.showProgress(1.0);
            return roi;
        }

        public int setup(String arg, ImagePlus imp)
        {
            image = imp;
            return BasePlugInFilter.DOES_8G | BasePlugInFilter.DOES_16 | BasePlugInFilter.DOES_32 | BasePlugInFilter.NO_CHANGES;
        }

        /** Determines whether to show status messages and a progress bar */
        public void showStatus(bool showStatus)
        {
            this._showStatus = showStatus;
        }
    }
}
